package leetcode_day._2021._202105._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/16 21:35
 * 数组中两个数的最大异或值
 * 算法：位运算  字典树  贪心
 * 构造字典树，字典树是一颗二叉树，左节点表示 0，右节点表示 1
 * 题目中限制了 nums[i] 是 32 位
 * 二进制高位为 1 会大于所有低位的和，比如二进制 1000 > 0111
 * 所以尽量使高位异或结果为 1
 * 另外假设 num[j] ^ num[i] 为最大值，那么一定有 i < j
 * 可能 num[j] 和后面元素的异或会大于 num[i]，但这是后面那个元素的事了
 * 所以遍历数组的时候，先把元素存入字典树中，然后再从字典树中取出能和该元素异或得到最大的值
 */
public class _16_421 {

    public int findMaximumXOR(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int tmp = nums[i] ^ nums[j];
                ans = ans > tmp ? ans : tmp;
            }
        }
        return ans;
    }

    class Node {
        Node[] node = new Node[2];
    }
    private Node root = new Node();
    void add(int x) {
        Node cur = root;
        for (int i = 31; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (null == cur.node[u]) cur.node[u] = new Node();
            cur = cur.node[u];
        }
    }
    int get(int x) {
        Node cur = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            // b 是期望得到的位
            int a = (x >> i) & 1, b = 1 - a;
            // 为 null 表示不存在
            if (null == cur.node[b]) {
                res |= (a << i);
                cur = cur.node[a];
            } else {
                res |= (b << i);
                cur = cur.node[b];
            }
        }
        return res;
    }
    public int findMaximumXOR_perfect(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            add(num);
            ans = Math.max(ans, num ^ get(num));
        }
        return ans;
    }

}
